package cn.edu.thu.thss.algorithm.structures;

import java.util.List;

/**
 * 搜索树的基本接口，其中K为树结点的键值类型，必须继承了Comparable接口，即支持大小比较，并且比较结果应遵循Comparable规范。V为结点的卫星数据
 * <p>这种数据结构不允许存在同样键值的节点，如果这样的节点被插入到<code>ISearchTree</code>所有的实现类中，会出现不可预料的错误(查找，插入，删除操作)
 * <p>这类数据结构的使用方式十分类似<code>java.util.HashMap</code>
 * @author EricPai
 * @param K 键值类型
 * @param V 卫星数据类型
 */
public interface ISearchTree<K extends Comparable<K>, V> {
	
	/**
	 * 从一棵查找树中查找到键值为key的结点
	 * @param key 要查找的键值
	 * @return 键值等于key的结点，如果不存在则返回<code>null</code>
	 */
	public TreeNode<K, V> search(K key);
	
	/**
	 * 从一棵查找树中查找到键值最小的结点
	 * @return 键值最小的结点，如果树中没有结点则返回<code>null</code>
	 */
	public TreeNode<K, V> minimum();
	
	/**
	 * 从一棵查找树中查找到键值最大的结点
	 * @return 键值最大的结点，如果树中没有结点则返回<code>null</code>
	 */
	public TreeNode<K, V> maximum();
	
	/**
	 * 从一棵查找树中查找到下一个键值<b>大于</b>key的结点
	 * @param key 要查找的键值
	 * @return 下一个键值<b>大于</b>key的结点，如果没有符合条件的结点则返回<code>null</code>
	 */
	public TreeNode<K, V> tranvseSuccessor(K key);
	
	/**
	 * 从一棵查找树中查找到下一个键值<b>小于</b>key的结点
	 * @param key 要查找的键值
	 * @return 下一个键值<b>小于</b>key的结点，如果树中没有符合条件结点则返回<code>null</code>
	 */
	public TreeNode<K, V> tranvsePredecessor(K key);
	
	/**
	 * 从一棵查找树中插入结点
	 * @param node 要插入的结点
	 * @return true 插入成功，当存在同样键值的结点时插入失败，返回false
	 */
	public boolean insert(TreeNode<K, V> node);
	
	/**
	 * 从一棵查找树中删除结点
	 * @param node 要删除的结点的键值
	 * @return true 删除成功，当不存在该结点时删除失败，返回false
	 */
	public boolean delete(K key);
	
	/**
	 * 返回该树的根结点
	 * @return 树的根结点，如果树中无结点则返回<code>null</code>
	 */
	public TreeNode<K, V> getRoot();
	
	/**
	 * 返回该树的高度
	 * @return 树的高度，当无结点时，返回0。仅有树根时，返回1
	 */
	public int getHeight();
	
	/**
	 * 返回该树的结点个数
	 * @return 树内的结点个数
	 */
	public int getNodesNum();
	
	/**
	 * 先根遍历
	 * @return 按先根遍历的顺序返回结果
	 */
	public List<TreeNode<K, V>> rootFirstTranverse();
	
	/**
	 * 按递减顺序遍历
	 * @return  按递减遍历顺序返回结果
	 */
	public List<TreeNode<K, V>> descTranverse();
	
	/**
	 * 按递增顺序遍历
	 * @return  按递增遍历顺序返回结果
	 */
	public List<TreeNode<K, V>> asceTranverse();
}
